P4555 [国家集训队]最长双回文串

显然是一道回文自动机板题。

L[i]L[i] 表示以 ii 号点为左端点的最长回文串 , R[i]R[i] 表示以 ii 号点为右端点的最长回文串。

L[i]L[i] 可以通过将回文串倒过来建自动机求得 , R[i]R[i] 可以直接用原回文串建自动机求得。

阅读全文 »

CF17E Palisection

答案为所有的回文串组合-不相交的回文串组合。

cntcnt 为回文串个数 , 可以通过计算每个节点的回文串数量求得。

不相交的回文组合也比较好求,先算出以 ii 为左端点和右端点的回文串数量 L[i]L[i] , R[i]R[i]

阅读全文 »

UVA1218 Perfect Service

一道很不错的树形dp。

dp[u][f]dp[u][f] 为以uu为根的子树。

f=0f=0,表示uu为服务器,那么uu的儿子和父亲既可以是服务器,也可以不是。

阅读全文 »

CF767C Garland

首先可以确定的是,如果点权和不为3的倍数,一定不存在合法方案。

记所有点权和为sumsum

容易想到,令 dp[u]dp[u] 表示以 uu 为根的子树的点权和 , 则有转移:

阅读全文 »

SP9934 ALICE - Alice and Bob

这道题的状态挺难设计的。。。

ss 为石子的总数,那么操作次数最多为 s+(n1)s+(n-1)

如果石子数量全不为一,那么先手必胜的条件为 s+(n1)s+(n-1) 为奇数,因为他一定可以保证操作 s+(n1)s+(n-1) 次。

阅读全文 »

UVA1500 Alice and Bob

这道题的状态挺难设计的。。。

ss 为石子的总数,那么操作次数最多为 s+(n1)s+(n-1)

如果石子数量全不为一,那么先手必胜的条件为 s+(n1)s+(n-1) 为奇数,因为他一定可以保证操作 s+(n1)s+(n-1) 次。

阅读全文 »